Conventionally, a packet relaying apparatus performing a traffic control controls an output rate of packets to be output (see, e.g., Japanese Patent Application Laid-Open No. 2007-88994). Because such a packet relaying apparatus provides QoS (Quality of Service) by application or by user, an increasing number of queues of buffer memory are implemented for each destination (see FIGS. 9A and 9B). Furthermore, to enhance flexibility of a bandwidth control and a priority control, the multi-stage configuration is adopted in the queue, resulting in further complication.
In the packet relaying apparatus which tries to realize the increased number of queues and meet the demand of multi-stage configuration, high-priority packets are preferentially output, and low-priority packets tend to stay in the packet relaying apparatus for a longer period of time. As a result, low-priority packets left without being output sometimes fill up a shared memory.
To avoid such inconvenience, packets of long staying time are sequentially discarded, starting from an earliest-received packet. Specifically, each shaper in the packet relaying apparatus discards the packet at the head of the queue independently.
However, when each shaper discards the packet of long staying time independently, even if a first shaper dequeues a packet in a specified bandwidth, a shaper of the next stage by way of which the discarded packet information has passed has its bandwidth remaining dropped. As a result, the efficiency of an output bandwidth of the shaper deteriorates.